package com.tyrone.algorithm.graph;

/**
 * 深度优先搜索
 */
public class DepthFirstSearch {
    private boolean[] marked;       //索引代表顶点，值表示当前顶点是否已经被搜索
    private int count;              //记录有多少个顶点与s顶点相通

    public DepthFirstSearch(Graph g,int s){
        marked=new boolean[g.V()];
        dfs(g,s);
    }
    /**
     * 使用深度优先搜索找出G图中v顶点的所有相通顶点
     * @param G
     * @param v
     */
    private void dfs(Graph G, int v){
        marked[v]=true;
        System.out.println(v);
        for (Integer w :G.adj(v)) {
            if (!marked[w]){
                dfs(G,w);
            }
        }

        count++;
    }

    /**
     * 判断w顶点与s顶点是否相通
     * @param w
     * @return
     */
    public boolean marked(int w){
        return marked[w];
    }

    /**
     * 获取与顶点s相通的所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }

}
